package com.atguigui.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 464.我能赢吗
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by  wangjiaxin  on 2022/5/22 20:32
 */
public class P464CanIWin {
    public static void main(String[] args) {
        Solution solution = new P464CanIWin().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        Map<Integer, Boolean> memo = new HashMap<Integer, Boolean>();

        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {

            // 公式计算所有数据的和是否大于 desiredTotal
            if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
                return false;
            }
            return dfs(maxChoosableInteger, 0, desiredTotal, 0);
        }

        /**
         * 记忆化搜索函数
         *
         * @param maxChoosableInteger 最大数
         * @param usedNumbers         从低位到高位
         * @param desiredTotal        条件
         * @param currentTotal        数字的和
         * @return
         */
        public boolean dfs(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal) {
            // 不包含
            if (!memo.containsKey(usedNumbers)) {
                boolean res = false;
                for (int i = 0; i < maxChoosableInteger; i++) {
                    // 判断是否为偶数
                    if (((usedNumbers >> i) & 1) == 0) {
                        if (i + 1 + currentTotal >= desiredTotal) {
                            res = true;
                            break;
                        }
                        // 递归调用
                        if (!dfs(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, currentTotal + i + 1)) {
                            res = true;
                            break;
                        }
                    }
                }
                memo.put(usedNumbers, res);
            }
            return memo.get(usedNumbers);
        }

    }
}
